import TreeNode from "../common/tree_node";
import { n1 } from "../common/tree_node";
//广度优先，左，右前后脚
//深度优先:从一个节点的左侧，一直遍历左侧


//距离一共三层：
//第一次遍历完queue = [2,3],list = [1]
//第二次遍历完 queue = [3,4,5],list = [1,2]
//第三次遍历完 queue = [4,5,6,7] list = [1,2,3]
//第四次遍历完 queue = [5,6,7] list = [1,2,3,4]

//思路:左节点想的是，你看完右边节点，要记得遍历我啊，不要继续遍历下去了，右边想的也是：所以本质是想有个先后顺序，队列明显是先来后到

function guangdu_loop(root: TreeNode | null): number[] {
    const queue = [root]//放节点
    const list:number[] = []//放所有的值
    while(queue.length) {
      let node = queue.shift() as TreeNode//先填满，再一个一个删掉
      list.push(node.val)
      if(node.left) {
        queue.push(node.left)
      }
      if(node.right) {
        queue.push(node.right)
      }

    }
    return list
};

// 深度优先搜索通常基于递归实现：
/* 前序遍历：*/
//list: [1]
//list: [1,2]
//list: [1,2]
//list: [1,2,4]//这时候，4的left是null，这时候就遍历到了4的兄弟节点
//list: [1,2,4,5]//最左边的最下面遍历完了，遍历倒数第二层最右边
//list: [1,2,4,5,3]
//list: [1,2,4,5,3,6,7]

let list:number[] = []
function preOrder(root: TreeNode | null): void {
  //终止条件
  if(root == null) {return}
  list.push(root.val)
  preOrder(root.left)
  preOrder(root.right)
}

/* 中序遍历：遍历到最底层再装值，然后装父节点，再装兄弟节点*/
//list: [4]
//list: [4,2]
//list: [4,2,5]
//list: [4,2,5,1]
//list: [4,2,5,1,6]
//list: [4,2,5,1,6,3]
//list: [4,2,5,1,6,3,7]


function inOrder(root: TreeNode | null): void {
  //终止条件
  if (root === null) {
    return;
  }
  // 访问优先级：左子树 -> 根节点 -> 右子树
  inOrder(root.left);
  list.push(root.val);
  inOrder(root.right);

}
function postOrder(root: TreeNode | null): void {
  //终止条件
  if (root === null) {
    return;
  }
  // 访问优先级：左子树 -> 根节点 -> 右子树
  inOrder(root.left);
  inOrder(root.right);
  list.push(root.val);

}
// preOrder(n1)
postOrder(n1)
console.log(list)

//总结前序:左边从头装到脚，然后装，倒数第一层右。然后装倒数第二层右的左。
//总结中序:装最左边的脚，然后装父节点，再装兄弟节点。然后装父节点的父节点


//      1
//  2       3
//4   5   6   7
//
